
% Alex - Template taken from Will Hossacks Latex page. Seems to fit the bill nicely.
% The stuff at the beggining can be largly ignored.
%
%
%                       This is a LaTeX 2e version of the
%                       laboratory project template file.
\documentclass[a4paper,11pt]{article}
\usepackage{fullpage,epsf}
\usepackage{graphicx}
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{appendix}
\usepackage{caption}
\usepackage{verbatim}
\usepackage{psfrag}
\usepackage{listings}
\usepackage{flafter}
\usepackage[pdfborder={0 0 0},colorlinks=true,linkcolor=black,citecolor=black,urlcolor=black]{hyperref}
\input{Qcircuit}  %Quantum circuit drawing


%
%                       This section generates a title page
%                       Edit only the sections indicated to put
%                       in the project title, your name, supervisor,
%                       project length in weeks and submission date
%
\begin{document}
\pagestyle{empty}                       % No numbers of title page                      
\epsfxsize=40mm                         % Size of crest
\begin{minipage}[b]{110mm}
        {\Huge\bf School of Physics\\ and Astronomy
        \vspace*{17mm}}
\end{minipage}
\hfill
\begin{minipage}[t]{40mm}               
        \makebox[40mm]{
        \includegraphics{crest.pdf}}
\end{minipage}
\par\noindent                                           % Centre Title, and name
\vspace*{2cm}
\begin{center}
        \Large\bf \Large\bf Junior Honours \\
        \Large\bf Computational Physics Project\\[10pt]                     % Change to MP/CP/Astro
        \LARGE\bf Simulating a Quantum Computer         % Change to suit
\end{center}
\vspace*{0.5cm}
\begin{center}
        \bf Alex Bush, Richard Inskip, Matt Cole, Jan Zaucha \& James Hancox\\ 
        March 2010                                    % Submission Date
\end{center}
\vspace*{5mm}
%
%                       Edit text for abstract
%                       
\begin{abstract}
        An implementation of a quantum computer was designed and constructed in Java
        with the key purpose of simulating Grover's algorithm, a quantum computational
        algorithm that searches for an element in an unordered list.
        Many new group and teamwork skills were also developed throughout the duration of the project.

	Both the simulation of the quantum algorithm and the development of group skills proved very 
	successful.
\end{abstract}

\vspace*{1cm}

                                 

%Removed stuff about declaration. If needed, it can be readded

\newpage
%
%                       End of Title Page
\pagestyle{empty}                               % No page numbers or TOC
\setcounter{page}{0}                            % Set page number to 0
\tableofcontents   
\newpage                             % Makes Table of Contents
\pagestyle{plain}                   %Now we want page numbers, wooo
%
%
%
%
%
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
%
%
%
%
%
%
%           REPORT BEGINS HERE, STUFF ABOVE JUST DEALS WITH STYLING
%
%
%
%
%
\section{Introduction}

In this project, we intend to collaboratively write a functioning simulator of a quantum computer. This simulator will be written in the Java programming language, and designed to implement Grover's algorithm for searching an unordered list. However, we will also design our code to theoretically be able to implement alternative algorithms with only a small amount of modification through careful object oriented design. All five members of the group will work together on the same code using collaborative tools such Google code, Eclipse and Subeclipse for SVN access.

\subsection{Aims}

Our project has several aims:
\\

% ANOTHER AIM WOULD BE TO GAIN AN UNDERSTANDING OF HOW A QUANTUM COMPUTER WORKS. SUITABLE AS 1ST AIM SUCH THAT EACH AIM BUILDS ON % THE PREVIOUS AIM. just put this in now as it is referred to later. Are the tenses correct here?
\textit{Develop an understanding of quantum computing.} This project is not just a computing project; it is a Computational Physics project. We not only aim to understand new aspects of coding, but also to understand our subject matter. Quantum computing is set to be an important aspect of Physics research in the near future, and an elementary understanding of the principles behind it will be of great use to us. 
\\

\textit{Implement a simulation of a quantum computer.} Using the Java programming language, we will write a generalized simulation of a quantum computer. Through object oriented techniques, we will write separate data objects for each quantum gate and for the quantum register, with common underlying mathematical features. 
\\

\textit{Simulate Grover's algorithm using our implementation of a quantum computer.} We will use our quantum computer to simulate Grover's algorithm for searching an unsorted list. As well as implementing the mathematics of the algorithm, we will design and create a Graphical User Interface (GUI) to provide an understandable graphical representation of the way in which Grover's algorithm works. 
\\

\textit{Learn group work skills and techniques.} For many of our team this is our first collaborative programming project. As such we will have to make use of tools and techniques we have not used before. Due to Java's object oriented programming style, we can decide on interfaces at the start of our project and then allocate certain sections of the simulator for each team member to work on (i.e. the GUI, the algorithm, the quantum gates, etc).
\\

\subsection{Background}

The idea of a universal quantum simulator was first proposed by Richard P Feynman in 1982 
\cite{feynman} . He noted that while any physics problem can be solved by any universal 
computing machine, not all forms of universal computer would be equally efficient for all 
problems. He demonstrated that a classical electronic computer is extremely inefficient when 
it comes to solving certain physical problems, and that instead a computer based on quantum 
mechanical principles would be able to perform the equations far more efficiently. 

David Deutsch developed these ideas further to describe a universal quantum computer in 1994
\cite{deutsch}; a Turing machine which uses a combination of the basic set of quantum gates 
(in a similar fashion to the standard binary logic gates) to solve any mathematical problem. 
After this was described, various others described algorithms which could be run on such 
a theoretical machine. In 1994, Peter Shor described a quantum algorithm which would factorise 
integers in polynomial time \cite{shor}; this was one of the first demonstrations of the 
potential power and efficiency of quantum computers. This was followed in 1996 by Lov K. 
Grover's algorithm for searching an unsorted database with \textit{N} entries in $O({N}^{1/2})$ 
time. We will be implementing Grover's algorithm in our simulator as part of our 
project. 

Progress in the field of quantum computing is not limited to theoretical algorithms and 
specifications. There have also been multiple working prototypes of quantum computers
constructed in labs around the world, working on a variety of different physical systems\cite{2010}. Quantum computing is clearly a very important field 
in the future of Physics. As the size of transistors in classical computers continues to shrink
and approaches the atomic scale, we can no longer rely on designs that ignore quantum effects;
we need designs which harness them. 

\newpage
\section{Theory}\label{theory}

%This section covers the theory of a quantum computer in some depth, before we move on to discuss our implementation of a quantum computer simulation.
% I commented this out since it looked a little out of place, i think we should either have a decent size paragraph or nothing. Can't find anything more relevant to say, feel free to uncomment it though
\subsection{Qubits, States and Registers}

In classical computation basic units of information are bits that can take values 0 or 1 in binary notation. The elementary difference between classical and quantum computing is that bits are replaced with quantum bits, also known as \textit{qubits}.

A qubit, due to its quantum nature can not only be 0 or 1, but also a linear superposition of these values.  According to the \textit{Copenhagen Interpretation} it is said that the qubit can be 0 and 1 simultaneously. Formally, in \textit{Dirac notation} the state of a qubit is given by: 
\begin{equation*}
| \psi \rangle = \alpha|0\rangle +  \beta|1\rangle
\end{equation*}
where $\alpha$ and $\beta$ are complex \textit{amplitudes}. Information about the state of the qubit can only be obtained by means of a measurement. The interpretation of the amplitudes of states is that upon measurement $|0\rangle$ is obtained with a probability of $|\alpha|^{2}$ and  $|1\rangle$ with probability of $|\beta|^{2}$. Hence, the usual normalization condition applies:
\begin{equation*}
 |\alpha|^{2}+ |\beta|^{2}=1
\end{equation*}
The states $|0\rangle$ and $|1\rangle$ are represented in matrix notation as 
$ |0\rangle = \begin{pmatrix} 
 1\\
0
\end{pmatrix}$ and $ |1\rangle = \begin{pmatrix} 
 0\\
1
\end{pmatrix}$, and form the \textit{computational basis}. Writing the state of a qubit in the form:
\begin{equation*}
| \psi \rangle = cos( \theta/2)|0\rangle +  e^{i\varphi}sin(\theta/2)|1\rangle
\end{equation*}
allows a general geometrical representation in the two-dimensional Hilbert complex space, known as the \textit{Bloch sphere}\cite{greenbook} (Figure \ref{bloch}).

\begin{center}
	\includegraphics[scale=0.75]{bloch}
	\captionof{figure}{Two-dimensional Hilbert space of a qubit represented by a Bloch sphere}
	\label{bloch}
\end{center}

A \textit{register} is a system of bits. In classical computing, a register containing $n$ bits can be in $2^{n}$ sharply defined states. In quantum computation, the quantum register can also be in any of these states, but additionally it can be in a linear superposition of any of the states.  Generally, for a $n$-qubit register, the computational basis consists of $2^{n}$ mutually orthogonal basis vectors, living in $2^{n}$-dimensional complex Hilbert space. 
By convention the basis vectors are written in binary form, i.e. for a 3-qubit register the basis vectors are:
\begin{equation*}
\{| 000 \rangle, | 001 \rangle, | 010 \rangle, | 011 \rangle, | 100 \rangle, | 101 \rangle, | 110 \rangle, | 111 \rangle \}
\end{equation*}



\subsection{Gates}
Just like classical logic gates such as AND or NOT, a quantum computer carries out changes on the state of a register by applying \textit{Quantum Gates}. A quantum gate is a reversible, unitary operation applied to the register to alter its state. Generally, most primitive gates act on single qubits. However, to construct a universal quantum Turing Machine capable of performing any algorithm, elementary gates acting on two qubits are also required. It is interesting to note, but will not be proved here, that the Hadamard \ref{had}, Any Phase \ref{anyp} and CNot \ref{cnot} gates form an infinite \textit{universal set of gates}\cite{universal}, meaning that any unitary $n$-qubit operation can be constructed purely from a number of these three gates. 

The action of gates on qubits in a given register is represented by a circuit. The horizontal lines correspond to particular qubits of the register. Gates are represented by boxes placed sequentially on the lines. For example:
\begin{equation*}
\Qcircuit @C=1em @R=1em {
      \lstick{\ket{\psi_1}} & \qw & \gate{E}  & \qw  & \qw \\
		\lstick{\ket{\psi_2}} & \qw & \qw & \qw  & \qw
}
\end{equation*}
\\
This example shows a gate \textit{E} acting on the first qubit in a register of two qubits.


\subsubsection{Hadamard Gate}\label{had}
The Hadamard Gate is one of the most useful gates in quantum computation and is used in the majority of algorithms. The Hadamard acts on a single qubit in a register and can be represented by the Hadamard matrix:

\begin{equation*}
H = \frac{1}{\sqrt{2}}\left( \begin{array}{ccc}
1 & 1\\
1 & -1\\
\end{array} \right)
\end{equation*}

The action of the Hadamard gate on a qubit in an arbitrary state $\left | \psi \right \rangle = \left( \begin{array}{ccc}
\alpha_0\\
\alpha_1\\
\end{array} \right) $ would give:

\begin{equation*}
\Qcircuit @C=1em @R=.7em {
     \lstick{\left | \psi \right \rangle} & \qw & \gate{H} & \qw & \qw & \rstick{\frac{1}{\sqrt{2}}\left( \begin{array}{ccc}
\alpha_0 + \alpha_1\\
\alpha_0 - \alpha_1\\
\end{array} \right)}
}
\end{equation*}
\\
The importance of the Hadamard gate lies in the application of the gate to a qubit in the state $\left | 0 \right \rangle$. When applied to $\left | 0 \right \rangle$ the Hadamard gate gives the superposition state $\frac{1}{\sqrt{2}}\left(\left | 0 \right \rangle + \left | 1 \right \rangle \right)$. Given a register of \textit{n} qubits in the state $\left | 0 \right \rangle$, if the Hadamard gate is applied to each qubit individually it will create a register containing a superposition of all possible $2^n$ states. This can be demonstrated with a register of size $n = 2$:

\begin{equation*}
\Qcircuit @C=1em @R=.7em {
     \lstick{\ket{0}} & \qw & \gate{H} & \qw & \qw & \rstick{\frac{\ket{0} + \ket{1}}{\sqrt{2}}}\\
          \lstick{\ket{0}} & \qw & \gate{H} & \qw & \qw & \rstick{\frac{\ket{0} + \ket{1}}{\sqrt{2}}}
}
\end{equation*}

The action of the Hadamard gate on each qubit gives the superposition of all the states as such:

\begin{equation*}
\left(\frac{\ket{0} + \ket{1}}{\sqrt{2}}\right) \left(\frac{\ket{0} + \ket{1}}{\sqrt{2}}\right) = \frac{\ket{00}+\ket{01} + \ket{10} + \ket{11}}{2}
\end{equation*}
\\
The action of applying the Hadamard gate to all $n$ qubits in the register is called the \textit{Walsh-Hadamard transform}\cite{nonphysicists} and is used in many algorithms to prepare the register so all states are in equal superposition.


\subsubsection{Phase Shift Gates}\label{anyp}
As mentioned earlier, the Phase Shift gates is another much needed quantum gate. The action of the any phase shift gate on a qubit is to phase-shift the $\ket{1}$ state by a complex factor\cite{tonypaper}. :

\setlength{\unitlength}{0.030in}
\begin{equation*}
\mbox{
\begin{picture}(30,0)(15,15)
  \put(-4,14){$\ket{1}$} \put(5,15){\line(1,0){20}} \put(20,15){\line(1,0){5}}
  \put(15,15){\circle*{3}}
\put(14,19){$\phi $}
\put(30,14){$e^{i\phi}\ket{1}$}
\end{picture}
}
\end{equation*}

The phase of the state $\ket{0}$ will not be changed. In matrix notation, the any phase shift gate is given as:

\begin{equation*}
\phi = \left( \begin{array}{ccc}
1 & 0\\
0 & e^{i\phi}\\
\end{array} \right)
\end{equation*}

There are also several important Phase Shift gates with specific phases shift values. The Phase gate has $\phi=\pi$:

\begin{equation*}
S = \left( \begin{array}{ccc}
1 & 0\\
0 & i\\
\end{array} \right)
\end{equation*}

The Pauli-Z gate has $\phi=\frac{\pi}{2}$ which gives the matrix:

\begin{equation*}
Z = \left( \begin{array}{ccc}
1 & 0\\
0 & -1\\
\end{array} \right)
\end{equation*}

Finally, the $\frac{\pi}{8}$ gate with $\phi=\frac{\pi}{4}$\footnote{Although the value of $\phi$ used is $\frac{\pi}{4}$, the gate is labelled the $\frac{\pi}{8}$ gate for historical reasons.} gives the matrix:


\begin{equation*}
\frac{\pi}{8} = \left( \begin{array}{ccc}
1 & 0\\
0 & e^{i\pi/4}\\
\end{array} \right)
\end{equation*}

\subsubsection{NOT Gate}
The quantum NOT gate is almost identical to the classical logic gate NOT. A classical NOT gate changes any 0 binary states to 1 binary states and vice versa. The quantum NOT gate is represented by the Pauli $X$ matrix:
\begin{equation*}
X \equiv  \begin{pmatrix} 
 0 & 1\\
1 & 0
\end{pmatrix}
\end{equation*}

The action of the NOT gate is given by the following:
%I made this into one line, seems better and less confusing this way.
\begin{comment}
\begin{equation*}
\ket{\psi} = \alpha \ket{0} + \beta \ket{1}
\end{equation*} 
becomes:
\\
\begin{equation*}
X\ket{\psi} = \beta \ket{0} + \alpha \ket{1}.
\end{equation*}
\\
\end{comment}
\begin{equation*}
X(\alpha\ket{0} + \beta\ket{1}) = (\beta\ket{0} + \alpha\ket{1})
\end{equation*}
This operation inverts the amplitudes of the two states of each qubit, hence inverts the probabilities of measuring each state. In Gate Notation the NOT Gate can be presented as:
\begin{equation*}
\Qcircuit @C=1em @R=1em {
      \lstick{\ket{0}} & \qw & \targ & \qw & \qw  & \rstick{\ket{1}}
}
\end{equation*}
\\

\subsubsection{CNOT Gate}\label{cnot}
The Controlled Not quantum gate is an extension of the Not gate with an addition of an extra parameter. Classically, the Controlled Not would invert the target bit if and only if the control bit was high ($=1$). In a quantum computer, the action of the CNot is such that the amplitudes of the states with control bit $\ket{1}$ are inverted with the corresponding amplitudes of the states with the opposite target bit. For example, a CNOT Gate applied to 2-qubit quantum register:
\begin{equation*}
\alpha \ket{00} + \beta \ket{01} + \gamma \ket{10} + \delta \ket{11}
\end{equation*}
becomes:
\\
\begin{equation*}
\alpha \ket{00} + \beta \ket{01} + \delta \ket{10} + \gamma \ket{11}
\end{equation*}
\\
This can also be represented in Gate Notation as:

\begin{equation*}
\Qcircuit @C=1em @R=1.5em {
       & \lstick{\ket{1}} &\ctrl{1} & \qw & \rstick{\ket{1}} \\	 
			& \lstick{\ket{0}} & \targ & \qw & \rstick{\ket{1}} \\
}
\end{equation*}
\\

The matrix given for a CNot gate with control qubit $0$ and target qubit $1$ is given as:

\begin{equation*}
\text{C} = \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
    \end{pmatrix}
\end{equation*}



\subsubsection{Toffoli Gate}
The Toffoli gate is a Controlled-Controlled-Not gate, and is very similar to the C-Not gate except that there is an additional control bit:

\begin{equation*}
\Qcircuit @C=1em @R=1.5em {
       & \lstick{\ket{1}} &\ctrl{1} & \qw & \rstick{\ket{1}} \\
		 & \lstick{\ket{1}} & \ctrl{1} & \qw & \rstick{\ket{1}} \\
			& \lstick{\ket{0}} & \targ & \qw & \rstick{\ket{1}} \\
}
\end{equation*}
\\

Like the C-Not, the gate will flip the target bit if both control bits are in state $\ket{1}$. For control bits $0$ and $1$ and target bit $2$, the Toffoli gate can be represented by the matrix:

\begin{equation*}
 \label{eqn12}
\text{T} = \begin{pmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
    \end{pmatrix}
\end{equation*}

As explained earlier, any unitary operation can be constructed from several CNot, Any phase and Hadamard gates, and the Toffoli gate is not exception. Its construction is explained by Lavor et. al. and is shown in figure \ref{biftof}.

\begin{center}
	\includegraphics[scale=0.9]{fig020}
	\captionof{figure}{The Toffoli gate composed of basic gates including the Hadamard, CNot and phase shift gates. $[\frac{\pi}{8}]^\dagger$ is the congugate $\frac{\pi}{8}$ gate and has $\phi=-\frac{\pi}{4}$.}
	\label{biftof}
\end{center}

\begin{comment}
\subsubsection{Measurement}
A measurement is not a unitary linear operator, but it is a very important element of a quantum computer. It allows the user to access a result of a computation, namely a state of the register, according to the probabilistic laws of quantum mechanics. The important thing to note is that during a measurement, the system cannot stay isolated and obtaining the information results in the collapsing of the wave function of the system, forcing it into the sharp state that had been obtained. Therefore, a measurement is never reversible and the output is always classical. It is treated as a gate, due to the fact that it affects the states of qubits. 
\end{comment}

\subsubsection{Measurement}\label{meas}
A measurement is not a unitary linear operator, but it is a very important element of a quantum computer. It allows the user to access a result of a computation by collapsing of the wave function of the system forcing it a sharp state in the register. The state measured is done so according to the probabilistic laws of quantum mechanics, with the states with the largest amplitude-squared having the largest probability of being measured.  As the system is \textit{forced} into a sharp state, a measurement is never reversible and the output is always classical. It is treated as a gate, due to the fact that it affects the states of qubits. 



\subsection{Quantum Algorithms}
Qubits stored in registers and a set of elementary quantum gates are all the ingredients needed to build a quantum circuit and hence a quantum algorithm capable of solving a problem.

As Feynman suggested, by utilizing the phenomenon of \textit{quantum interference} (superposition of states), quantum algorithms are able to successfully complete computations which would classically require unavailable amounts of computational resources (computation time). 

 In general, a quantum algorithm requires one or more registers with initial classical input (qubits are assumed to be initially in a sharp state) \cite{algorithms}. A series of gates is applied to the register which transforms it into a state with a high probability of yielding the desired result upon measurement.  It should be emphasized that, due to its nature, a quantum algorithm is not always successful, i.e. completing the same circuit does not always measure the same output. This generally should not be a problem, as the efficiency gain of quantum algorithms over classical computation is usually qualitatively high enough to assume the need of repeating computations. 

\subsubsection{Grover's Algorithm}\label{grovthe}

In 1996 Lov Grover published ``A fast quantum mechanical algorithm for database search'', although the title of the publication is misleading\footnote{Currently, one must know the data they are searching and hence is little use as database search.}. This algorithm is a fundamental demonstration of the power of quantum computing \cite{grover}. More adequately it is referred to as a search algorithm of an unordered list.

\paragraph{Problem Structure}
Given there are $N$ elements in an unordered list, with each element given by $x_i$ (where $i$ is the element index number). Suppose we define $f(x)$ to denote a function that determines whether $x_{i}$ satisfies a given search criterion. We set $f(x)$ such that it returns 1 if the search condition is satisfied and 0 otherwise. 
The problem is to find a searched value $x_{s}$ such that $f(x_{s})=1$. This search algorithm requires that all the elements on the list are initially known and there is a way of assessing whether or not a trial is correct. 

Classically one would have to exhaustively evaluate the function for each element separately, with probability of success $(N-(i-1))^{-1}$ for the $i^{th}$ trial. On average, the answer would be obtained after $N/2$ trials, corresponding to number of steps of order $ \Omega(N)$. Grover's algorithm, relying on the superposition of states of qubits, evaluates the function for all elements simultaneously. However, quantum information is not instantly available for the user. The information can only be retrieved by means of a measurement and $O(\sqrt{N})$ steps are required to arrive at a state with a high probability (at least $1-N^{-1}$) of measuring the right answer \cite{librarybook}.  

\paragraph{Algorithm Setup}

A register of $n$ qubits all in sharp state $|0\rangle$ is initialized. Each state corresponds to an element of the unordered list. Thus, for $n$ qubits the register holds $2^{n}=N$ elements.

The register is prepared by applying the Hadamard gate  to all qubits. This is also referred to as the Walsh-Hadamard transform $H_{n}$. As a result, all states have the same amplitude and hence probability of being measured. 

\begin{equation*}
| \psi \rangle \equiv H_{n}|00...0\rangle=  \frac{1}{ \sqrt{N} } \sum_{i=0}^{N-1} |i\rangle
\end{equation*}

\paragraph{Performing The Algorithm}

At this point the Grover iterate can begin.
The Grover iteration is divided into 2 subroutines:

\begin{enumerate}
\item
The Marking Subroutine. 
This subroutine requires the use of an oracle $U_{f}$ which marks the searched element with a  negative sign. 
Formally for the oracle to work, an additional register with an auxiliary qubit is required. 

The action of the oracle is defined by the following: 
\begin{equation*}
|x \rangle |q \rangle \stackrel{U_{f}}{\longrightarrow} | x \rangle | q \oplus f(x) \rangle
\end{equation*}
where $|x \rangle$ is the state of the first register, $|q \rangle$ is the state of the auxiliary qubit and $\oplus$ is addition modulo 2. This means that the auxiliary qubit is flipped if $f(x)$ yields 1. 

Let the second register contain an auxiliary qubit initially in state $|1 \rangle$. Then apply the Hadamard gate to this qubit leaving it in an eigenstate $|1\rangle-|0\rangle \equiv |-\rangle$ (having ignored the normalisation). For $x_{i} \neq x_{s}$ the oracle does not have any effect. But when $x_{i } =x_{s}$ the auxiliary qubit is flipped. Thus, the action of the oracle can be written as:
\begin{equation*}
|x \rangle |- \rangle \stackrel{U_{f}}{\longrightarrow} (-1)^{f(x)}| x \rangle | -  \rangle
\end{equation*}
It should be noted that the state of the auxiliary qubits remains unchanged. This means that the effect of the oracle is that of a unitary matrix $I-2|x_{s} \rangle \langle x_{s}|$ operating only on qubits in the first register. Therefore, in simulations of Grover's algorithm the auxiliary qubit may be omitted. 

\item
The inversion about mean. This subroutine consists of 3 gates: The $H_{n}$, ``Nand-All'', $H_{n}$. The Nand on all qubits returns false only if all qubits are in state $|0 \rangle$. We define this gate to apply a phase shift of -1 to all states which return true. In effect all states, except the ground state, are phase shifted by $-1$.  Thus, ``Nand - All'' can be written as a unitary matrix $2|0 \rangle \langle 0|-I$.

Lavor et. al. show how ``Nand - All'' can be decomposed in terms of basic elementary gates\cite{lavor} (Figure \ref{lavorfig}).

\begin{figure}[h]
    \setcaptionmargin{.5in}
    \centering
    \psfrag{psi0}{$\sket {\psi_0}$}
    \psfrag{psi1}{$\sket {\psi_1}$}
    \psfrag{psi2}{$\sket {\psi_2}$}
    \psfrag{psi3}{$\sket {\psi_3}$}
    \psfrag{psi4}{$\sket {\psi_4}$}
    \psfrag{psi5}{$\sket {\psi_5}$}
    \psfrag{iI}[][]{$iI$}
    \includegraphics{lavorfig.pdf}
    \caption{The ``Nand - All'' gate composed of basic gates; the Hadamard gate, Pauli-X gate, All-CNot (composed itself of CNot) and complex identity gate.}
    \label{lavorfig}
\end{figure}

Also worth noting is that:
\begin{equation*}
H_{n}(2|0 \rangle \langle 0|-I)H_{n}=2| \psi \rangle \langle \psi| -I
\end{equation*}
where $| \psi \rangle$ is the equally weighted superposition of states. This is why $H_{n}$(Nand-All)$H_{n}$ is referred to as the inversion about mean. 
\end{enumerate}

\noindent The two subroutines described above give a Grover iteration $G$:
 \begin{equation*}
G \equiv (2| \psi \rangle \langle \psi| -I)U_{f}
\end{equation*}

It is also insightful to explain the geometry of Grover's iteration \cite{deutschvideo}.  Consider the two-dimensional plane through the $N$-dimensional Hilbert space of the n qubits containing the searched state $|x_{s} \rangle$ and the superposition of states $| \psi \rangle$. For higher numbers of qubits these states are nearly orthogonal - their scalar product is $\langle x_{s}| \psi  \rangle  = N^{-1/2} $. Now, define a state $| \phi \rangle$ orthogonal to the searched state, such that $\langle x_{s}| \phi  \rangle  = 0$. Note that all  states in the described plane can be given as $cos(\theta)| \phi \rangle + sin(\theta)| x_{s} \rangle$, where $\theta$ is real. For a general state $|x(\theta) \rangle=cos(\theta)| \phi \rangle + sin(\theta)| x_{s} \rangle$, the action of the oracle yields $U_{f}|x(\theta) \rangle=cos(\theta)| \phi \rangle - sin(\theta)| x_{s} \rangle$. Therefore it is clear that the action of the oracle is geometrically a reflection about the vector of state $| \phi \rangle$. As explained above, the second subroutine of the grover iteration is the inversion about mean. Thus, geometrically it is the reflection about the vector of state $| \psi \rangle$. The two reflections together yield a rotation in the direction of the searched state, as indicated in Figure \ref{rotfig}. 

\begin{figure}[h]
    \setcaptionmargin{.5in}
    \centering
    \includegraphics[scale=0.4]{drawing.pdf}
    \caption{The Grover iteration represented as a rotation of $\ket{\psi}$ towards the searched state $\ket{x_s}$.}
    \label{rotfig}
\end{figure}

Let $\theta_{1}$ be the angle between the vectors $| \psi \rangle$ and $| \phi \rangle$. Recalling that $\langle x_{s}| \psi  \rangle  = N^{-1/2} $, it follows that $cos(\pi/2-\theta_{1}) = N^{-1/2} $ and hence $\theta_{1}=arcsin(N^{-1/2} )$.  From figure it is visible, that each Grover Iteration rotates the state vector of the register by $2\theta_{1}$ in the anti-clockwise direction. A measurement of the register yields the correct answer with high probability only after the state vector of the register has rotated close to the searched state. This means that the measurement should be made after a particular, $N$-dependent number of iterations $r$:  

 \begin{equation*}
r=CI \left( \frac{arccos( N^{-1/2})}{2\theta_{1}} \right)
\end{equation*}
where $CI(x)$ is defined as the integer closest to the value $x$, with the convention that $\frac{1}{2}$ is rounded down.

An interesting fact is that the efficiency of Grover's Algorithm cannot be improved. This was demonstrated shortly after the publication of Grover's original paper by Bennet et. al. \cite{bennett}. Another thing to note is that Grover's algorithm can be easily generalized to a case in which multiple values $x$ exist, such that $f(x)=1$. However, the more values that satisfy the search criterion exist, the lesser is the efficiency gain in comparison with classical computing \cite{boyer}. 


\newpage
\section{Implementation}
The theory of Grover's Algorithm has already been explained in detail (section \ref{theory}), however as mentioned previously, the main aim of this project is not simply to gain an understanding of the theory. It is more important that we apply this theory to ensure that a working quantum computer simulator is produced. The implementation of such a task in an object oriented environment can be performed in a variety of different ways. The method chosen here was to produce a modular class structure that also maps naturally onto the problem. The UML class diagram for the program can be found in the appendix (section \ref{uml}) describing the structure and interaction of the components. In the following sections, this structure is explained, along with a description of how Grover's Algorithm is effectively implemented by the simulator.


\subsection{Program Description}
Upon running the program, the user is presented with a small dialogue frame allowing the input of the desired number of qubits in the register and search element. Note that these are limited to reasonable values such that computation is feasible, displaying appropriate error messages if the user input is outside these feasible bounds. After entering valid input parameters, the user is taken to the main window and the register is set to the sharp state $|0\rangle$. The main window consists of 4 panels:
\begin{itemize}
\item Output text box for printing the operations performed on the register.
\item Probability plot showing the probability associated with each of the registers states.
\item Vector diagram showing the 2D cut of the Hilbert space. This is the geometrical interpretation referred to in section \ref{grovthe}.
\item Options panel used to choose functional or matrix representation of gates (see section 3.5). Also allows the selection of basic gates whereby only elementary gates are applied to the register (complex gates such as the nand gate are constructed from basic gates). % This is my understanding of the code. Please correct if required.
\end{itemize}
As explained in \ref{grovthe}, a Hadamard gate must first be applied to each qubit in order to prepare the register. Upon clicking the ``Next Step'' button, a Hadamard is applied with the required target bit. This will continue to happen until the register is prepared at which point the ``Next Step'' button will apply a Grover iteration (see 3.6.4 Grover Iteration) to the register. The measure button can be used at any time and applies the measurement gate (section \ref{meas}) to the register. All output panels are updated in real time after every user interaction. 


\subsection{Structure}
The structure of the program was designed very early on in the development process, remaining mostly unaltered for the duration of the coding period. The UML diagram \ref{uml} was produced before any coding took place, ensuring a sound understanding of class interaction from the beginning of the project. Once the the basic structure was decided, empty classes and interfaces were defined and packaged accordingly. It was then a case of assigning the various components of the project to individual team members (see section 4.3 for details on team management). The chosen package structure allows for code to be easily reused in similar projects, i.e. in the implementation of other quantum algorithms. A packaged modular support structure allows specific aspects of the program to be swapped in and out of the simulator providing simplified extendibility in the future. This is particularly true of the \texttt{gates} package detailed in section 3.5 which may be used to simulate any quantum algorithm. Additions to the simulator include the \texttt{Matrix} and \texttt{Complex} classes which were also chosen to be packaged separately (\texttt{mathtools} package) to allow for use in any future development. Both classes providing a large selection of matrix and complex operations, such as tensor products, complex addition e.t.c.


\subsection{GroverCircuit}
The class \texttt{GroverCircuit} is the main controlling body; it is responsible for handling the other components of the program. The key fields in the class are \texttt{reg} (the quantum register) and \texttt{UI} (the user interface). After instantiating these objects, \texttt{GroverCircuit} applies gates to \texttt{reg} depending on the user input, passing the updated register to \texttt{UI} to be displayed. \texttt{GroverCircuit} is an action listener added to the buttons on the user interface. When a button is clicked the appropriate gate is generated and applied to the register via one of the following methods:
\begin{itemize}
\item  \texttt{prepareRegister()} - If the register has not been fully prepared (i.e. the Walsh-Hadamard transform has not yet been completed) a Hadamard gate is applied to the register with the appropriate target bit.
\item  \texttt{performIteration()} - If the register has been prepared, this method will be called to perform the next iteration of Grover's Algorithm on the register.
\item  \texttt{measureRegister()} - When the ``Measure'' button is clicked on the UI, this method performs the probabilistic measurement of the register.
\end{itemize}
All of the above 3 methods return objects of type \texttt{String} which detail the action taken on the register. In this way, information about each step is easily passed to the output text area. The way in which the gates are applied to  \texttt{reg} is through the use of a factory class gate generator. This is an important feature of the code, making it non specific to the Grover's implementation used here. 


\subsection{Register}
The \texttt{Register} class represents the quantum register. It is an extension of the  \texttt{Matrix} class within the  \texttt{mathtools} package. In this way, the register is a special case of a matrix, containing additional methods used mainly when applying gates and measuring. Notable methods include the  \texttt{update(Matrix)} and  \texttt{update(Complex[])} methods which are called by matrix and functional gates respectively when they are applied to the register. The class also contains methods to reset the register to the ground state, return the probability of a given state and return the state with probability 1 (for use only after a measurement gate is applied).


\subsection{User Interface}
The user interface contains two main display panels, the \texttt{ProbPlot} panel and the \texttt{VectorPlot} panel. The first of these panels displays the current amplitudes of each quantum state in the register, and the second showing a 2D cut of Hilbert space as referred to in section 2.3.1. The \texttt{VectorPlot} panel is an extension of the class \texttt{Plot} from the Ptolemy plotting package. This package provides many convenient methods for drawing mathematical diagrams and plotting scientific results, making it well suited to this usage. The \texttt{ProbPlot} panel was also initially an extension of the \texttt{Plot} class, but it was found that this was causing significant slowdown in the program. Ptolemy draws each individual point on the graph to the screen, instead of buffering them and then drawing them all simultaneously; when running the program for a 16 qubit register this meant that \texttt{ProbPlot} was drawing to the screen 65,536 times for each iteration. As such this class was rewritten to not use Ptolemy components, and only use Swing and AWT components; this lead to a significant improvement in the performance of the program. 

The user is given the option of ``Matrix Representation'' and ``Functional Representation''. This alters the way in which the program handles \texttt{Gate} objects. The difference between the two is discussed in more detail below.


\subsection{Gates}
% This first paragraph is by me (Matt). The rest of this section was written by Jan. Looks like you saved me a lot of work Jan, glad you emailed me this today!
The most noticeable feature of code structure is the instantiation of the gate objects. All the constructors of the gates are protected and therefore gates can only be created by calling static factory methods in the \texttt{Factory} class. An explanation of factory methods and the purpose for using them in our project is explained in the appendix (section \ref{factory}). All gate objects extend one of two abstract base classes. These are  \texttt{MatrixGate} and \texttt{FunctionGate} both of which inherit from the \texttt{Gate} interface. The only exception to this rule is the \texttt{CompositeGate} which contains an array of either matrix or function gates (or a combination of both).  \texttt{CompositeGate} inherits directly from the  \texttt{Gate} interface. When a composite gate is applied to the register, it applies each of its gates in order.

The gates were implemented in two ways: explicitly in matrix form and as a function altering the states of the register. 
Each gate implementation followed a simple structure of a \texttt{Gate} interface extended by either \texttt{FunctionGate} or \texttt{MatrixGate}. The Gate interface specifies that each gate must have have an \texttt{apply()} method which could be used to apply it to the register. Other house keeping methods such as \texttt{getName()} were also included in the interface. The extension of the interface to either \texttt{FunctionGate} or \texttt{MatrixGate} provided the parameters check \texttt{isFunctional()} allowing simplified checking of the Gate type in use.

The \texttt{factory} class is responsible for constructing the gate objects according to the \texttt{functional} parameter specified by the user. Additionally the user may choose to create complicated gates (such as Toffoli) out of a sequence of basic gates.

\subsubsection{Matrix gates}
Applying a \texttt{MatrixGate} to a single qubit is simply multiplying the state vector of that qubit by the matrix of the desired gate. If the register contains more qubits, then it is impossible to apply a $2\times2$ matrix to it. Generally, during each step of a computation it is assumed that a gate is applied to all qubits. The gate applied to the qubits which are not to be affected is an identity $I$. Thus, for a register containing 5 qubits and an arbitrary gate $GATE$ acting on the second qubit, the matrix $M$ applied to the register is given by:
 \begin{equation*}
M=I \otimes GATE \otimes I \otimes I \otimes I 
\end{equation*}
where $\otimes$ denotes \textit{tensor product}.

A matrix gate acting on a pair of qubits can be applied to a larger register in a similar fashion, provided the two qubits affected are close neighbours (i.e. lie on adjacent lines in circuit notation). If the gate is to be applied to two separated qubits, the matrix to apply cannot be created in such a straightforward way \cite{radtke}.

After a thorough analysis of the CNOT gate we arrived at a formula to create a matrix representation for non adjacent control and target qubits: 

\subsubsection{Example: CNOT gate}
The Gate is constructed by the addition of two matrices, A and B. Each matrix depends on a combination of an outer product and the 2x2 identity matrix and the 2x2 Not matrix. The number of operations for each of the matrices is proportional to the number of qubits in the register where both matrices A and B will have equal number of operations. The matrix A has a total of $(N-1)$ tensor product operations of the 2x2 Identity matrix, where N is the number of qubits in the register, and one operation of the outer product of two one qubit states ($\ket{0}\bra{0}$). The position of the outer product is dependent on the specified control bit of the Gate. 

The matrix B has a total of $(N-2)$ Identity operations with an outer product operation and a Not operation. The outer product for matrix B is $\ket{1}\bra{1}$, and the position is the same as for matrix A. (Again, a total of N operations) The position of the Not operation is dependent on the specified position of the target qubit. The Cnot matrix is then the addition of matrices A and B.

For example the Cnot applied to a 4 qubit register(qubits 0,1,2 and 3) with control bit 1 and target 2 would become:
\begin{equation*}
A = I \otimes \ket{0}\bra{0} \otimes I \otimes I
\end{equation*}
\begin{equation*}  
B = I \otimes \ket{1}\bra{1} \otimes NOT \otimes I
\end{equation*}
\begin{equation*}
GATE = A + B
\end{equation*}

\subsubsection{Function gates}
Due to the fact that matrices applied to larger registers contain a parabolically growing number of elements, each of the elements being a complex number which requires two float point numbers to store it, the memory demand of matrix operators for larger registers is huge. For a 16 qubit register, each gate is represented by a 65536 x 65536 matrix, in which each entry consists of two 32-bit \texttt{float}s. This means that in order to represent a single 16-qubit gate in matrix form, 32 GB of RAM would be required, and each iteration of Grover's Algorithm requires four separate gates. Worth noting is that a great majority of the matrix elements are zero anyway. In reality, quantum gates may be simulated in a much more efficient fashion by simply adjusting the amplitudes of the register in accordance with the defined action of a given operator. 

The single qubit \texttt{FunctionGates} can easily be implemented with the help of \textit{Walsh functions} \cite{walshfunc}. Depending on the target qubit, the amplitudes of the register are adjusted in patterns resembling functions from the Walsh basis orthonormal set. 

Function gates for two or more qubits (CNOT as well as Toffoli) become exponentially more complicated to implement with the use of Walsh functions. Therefore we decided to determine how the amplitude of each state is affected by utilizing java's bitwise shift operators. 

\subsubsection{Composite gates}
Composite gates were implemented as an array of basic gates applied one by one in the correct order. A composite gate may be thought of as a ``mini circuit''.

\subsubsection{A list of implemented gates}
The following table shows the gates included in the gates package. All gates of the universal set were implemented extending both \texttt{MatrixGate} and \texttt{FunctionGate}:

\newcommand{\yes}{\checkmark}
\begin{center}
	\begin{tabular}{|l|c|c|c|}\hline
		Gate & Matrix & Functional & Composite \\\hline
		Hadamard & \yes & \yes &  \\\hline
		Phase Shift & \yes & \yes &  \\\hline
		C-Not & \yes & \yes &  \\\hline
		NOT/Pauli X & \yes & \yes &  \\\hline
		Pauli Y & \yes & \yes &  \\\hline
		Pauli Z & \yes & \yes &  \\\hline
		Measurement &  & \yes &  \\\hline
		Toffoli &  & \yes & \yes \\\hline
		Oracle & \yes & \yes &  \\\hline
		Nand & \yes & \yes & \yes \\\hline
		All C-Not & \yes & \yes &  \\\hline
		Complex Identity or $iI$ & \yes & \yes &  \\\hline
		Grover Composite &  &  & \yes \\\hline
	\end{tabular}
	\label{table}
\end{center}

\noindent Note that:

\noindent \texttt{AllCnot} is a gate, which acting on an $n$-qubit register takes the first $n-1$ qubits to be control qubits and the $n^{th}$ qubit as the target qubit. This gate can be considered as a generalized Toffoli gate; Lavor et. al show how it can be built out of a sequence of Toffoli gates (which have also been coded as a combination of gates from the universal set), but it requires the use of auxiliary qubits. Therefore, it has been decided only to code it in a naive way. 

\noindent The \texttt{ComplexIdentity} is resembles an Identity Matrix, but the entries are purely complex. 

\noindent The \texttt{GroverComposite} is simply a Grover Iteration. 

\subsection{Grover's Iteration}
It has now been explained how the code was written to allow for a register of specified size to be created, for gates to be applied to the register and for the resulting register state to be displayed graphically (the second project aim as previously mentioned). Once this was achieved, it was then a case of using the tools to simulate the Grover Algorithm.

The theory in section \ref{grovthe} includes vital definitions for the two sub routines of Grover's Algorithm.
\begin{itemize}
\item \textit{Marking} - it is concluded that the effect of the oracle is that of a unitary matrix  $I-2|x_{s} \rangle \langle x_{s}|$ acting on the register.
\item \textit{Inversion about the mean} - it is concluded that this is achieved through the application of a Hadamard transform gate followed by a nand gate followed by another Hadamard transform gate.
\end{itemize}
The result of the above two definitions is that a Grover iterate can be created by the application of 4 gates to the register. The class  \texttt{GroverComposite} extends \texttt{CompositeGate}, setting its gates to that mentioned above:

\texttt{groverIteration[0] = oracle;}

\texttt{groverIteration[1] = hadamardTransform;}

\texttt{groverIteration[2] = nand;}

\texttt{groverIteration[3] = hadamardTransform;}

\noindent Note that the nand gate will also be a composite of basic gates if the user has checked the ``Use Basic Gates'' tick box on the options panel.

\begin{comment}
\subsection{More Gate Stuff - see comment in code} % Jan i think this is yours? This was here before i replaced it with the stuff you sent me today. Maybe you want to add it to the Gate section above. All the material is here, so anyone feel free to move it around.
Little bit of text about gates, can mention that we packaged them, with gate interface (use apply method to use as defined in interface) and with factory constructor, however details on factory constructors in appendix. Also talk about how gates can be represented as own gate or several basic gates and we accomodate for this.
\\
\\
\\
The implementations of the gates followed a simple structure of a Gate interface extended by either Functional or Matrix Gate and then extended by the gate to be coded(as seen from the uml). The Gate interface specifying that each gate would have an "apply()" method which could be used to apply the operator(Gate) to the register. Other house keeping methods such as "name()" were also included in the interface. The extention of the interface to either Functional or Matrix provided the parameters check "isFunctional" allowing simplified checking of the Gate type in use.
\\
The factory methods were also coded to allow simplified switching between the functional and matrix representation. 

\subsubsection{NOT Matrix}
The NOT Gate is constructed by applications of the tensor product between the 2x2 matrix representation of NOT;
\[ \left( \begin{array}{ccc}
0 & 1\\
1 & 0\\
\end{array} \right)\] 
...and the 2x2 Identity Matrix;
\[ \left( \begin{array}{ccc}
1 & 0\\
0 & 1\\
\end{array} \right)\] 
 The number of applications of the tensor product is proportional to the size of the Quantum Register. For the specified target qubit, I (the identity 2x2 matrix) was applied to the left of NOT matrix target applications. For example for a specified target = 2, I would be applied to the left of NOT twice. I was then applied to the right of Not (numQubits - (target+1)) applications. For example for a 4 qubit quantum register, with target=2, another one application of I would be applied to the right of Not. For this example the generation equation is:
\begin{equation*}
GATE = I  \otimes  I  \otimes  NOT  \otimes I
\end{equation*}
Which produces a 16x16 matrix which can been applied to the register.


\subsubsection{CNOT Matrix}
The Gate is constructed by the addition of two matrices, A and B. Each matrix depends on a combination of an outer product and the 2x2 identity matrix and the 2x2 Not matrix. The number of operations for each of the matrices is proportional to the number of Qubits in the Register where both matrices A and B will have equal number of operations. The matrix A has a total of (N-1) tensor product operations of the 2x2 Identity matrix, where N is the number of Qubits in the Register, and one operation of the outer product of two one Qubit states. Ie. The outer product of $\ket{0}\bra{0}$. (A total of N operations.) The position of the outer product is dependent on the specified Control bit of the Gate. 
\\
The matrix B has a total of (N-2) Identity operations with an outer product operation and a Not operation. The outer product for matrix B is $\ket{1}\bra{1}$, and the position is the same as for matrix A. (Again, a total of N operations) The position of the Not operation is dependent on the specified position of the target Qubit. The Cnot matrix is then the addition of matrices A and B.
\\ 
For example the Cnot applied to a 4 Qubit Register(Qubits 0,1,2 and 3) with Control bit 1 and target 2 would become:
\begin{equation*}
A = I \otimes \ket{0}\bra{0} \otimes I \otimes I
\end{equation*}
\begin{equation*}  
B = I \otimes \ket{1}\bra{1} \otimes NOT \otimes I
\end{equation*}
\begin{equation*}
GATE = A + B
\end{equation*}

\subsubsection{Matrix or Functional Representation}
Explain why we need to do this (Hint matrix will be very intensive) and which gates we made this available for.
\subsubsection{Grover Algorithm}
Talk about this, how it is built from gates and using booleans can be represented by matrix or functional gates.

Talk a little about what is represented (rotation of states) but point to appendix for more discussion for GUI. Can talk about how circuits are not generalisable and there will never be a general display for algorithms unlike our set of gates.
\\
\\
\\
Before beginning to simulate the Quantum Computer we first reviewed a design structure of the best way to represent gates and algorithms in the simulator as well as being extendible. The UML diagram available in the appendix defines some of the choice we made. The choice had been made to have both functional and matrix representations of the gates/algorithms and also where possible create composite gate of basic gates. In other words, produce more complex gate by construction of a circuit of basic gates.
\\
\end{comment}

\newpage
\section{Discussion}
As this third-year project was the \textit{first} group computing project any of the members had undertaken, additional emphasis was put into methods of managing workload across the team. This led us to adopt the use of many new tools such as Java documentation (\ref{javadoc}), version controlling such as Subversion and using development environments such as Eclipse (\ref{svn}).
\subsection{Development Structure}
Given our initial lack of understanding of quantum computing and equally our lack of experience working on such a large project, at first development on the project had no real focus. The aim of the opening several weeks were to gain as much understanding as possible into quantum computing and for us each to begin prototyping our own ideas. It became apparent very soon that much code duplication would be prevented if certain elements of the code that were common across all prototypes could be packaged. For example, from initial reading of the subject, quantum computing has great dependence on matrices and matrix operations. Similarly, all values in a quantum computer, by the very nature of quantum mechanics, have to be represented by complex numbers. Both the \texttt{Matrix} and \texttt{Complex} classes were developed first and packaged in \texttt{mathstools} for use in all other programs and prototypes.

Once having a greater understanding of the project and how it should be developed, a unified design was agreed upon and drawn using the Unified Modelling Language (see appendix \ref{uml}). Although the design was subject to some change throughout the span of the project, it was possibly the most important step in projects development as it allowed for each group member to develop different areas of the project. With a solid design including interfaces\footnote{interfaces} and object-orientation, all five group members managed to work simultaneously on the project towards a single goal. This allowed members to specialise on certain aspects of the simulation, for example designing the quantum gates, and hence increase work flow.

%
%Mention how we started off with prototypes each, but all contributed to trunk slowly, maths tools were universal so theres %were developed first and build from there.
%
%By the end of the project, all 5 members were submitting significant contributions to the final project.

\subsection{Javadoc}\label{javadoc}
Javadoc is an API documentation generator by Sun Microsystems, the de facto standard for documenting Java source code. The Javadoc generates static HTML pages that, if the code was commented properly, give the reader all the information they would need to know about the class the documentation belongs to. Javadoc played a very crucial role in the development of our code for several reasons.

Firstly, as all five members of the group could be working on different sections of the code independently the documentation allowed any member of the group to understand everybody else's code without having to spend a lot of time reading through the code itself. A member of the team could quickly understand how someone else's code could be used within their code, how different classes could be initialised and all the methods that were available to them once an object had been created. Furthermore, the documentation is completely unified and hence someone who is not a member of our team would know exactly where to look to understand our code and use it within a project their our own. The Javadoc provides API documentation and hence anybody could, for example, import our compiled \texttt{Gate} package without having source code but still have access to all the information necessary to use the classes in the package.

\subsection{Team Management and Code Development Tools}\label{svn}
To allow our team of five to work on the project simultaneously, it was very sensible that we invest a little time in researching tools that would make the development of the project as trouble free as possible. The first problem we had to confront was that of sharing the code between each project member.

It was initially very evident that sharing code by means of email or file-server would not be wise and so we researched how such a problem is confronted in industry. There have been many applications to solve this problem of code management and are usually developed under the title of version-control systems. A widely used and open-source implementation a version-control system is Subversion (SVN). This is the application we opted for. Its design is very simple but effective; a user \textit{checks out} a working copy (latest version) of the code from a repository hosted on a server, he can then make changes to the code and then \textit{check in} his code to the repository. The server he checks in his code to will note all the changes he had made to the files save the new versions of the files. The old versions of the files are removed. From these new versions of the files and the changes made, historical revision can be reproduced on demand. All revisions of the files can be reproduced regardless how many times a file has been edited and checked in. If a section of the code becomes broken after a new revision one can easily revert back the changes or examine the changes between the versions to see where the error might have appeared. Also, if a users working copy becomes out of date (somebody might have checked in after the working copy was checked out) he can easily update his working copy to the latest version whilst keeping his local changes. This application managed to solve all our code management problems, however SVN is simply an application and must be hosted somewhere.

There are many SVN hosting solutions, ranging from hosting on University workspace to paid hosting, but we opted for a very popular free solution, Google Code. Google have provided a very reliable SVN hosting product with many additional tools that were very useful to our project. As well as allowing all our team members to check in and check out the project files, all the changes made between files were visible on a web-based project centre. Google Code also offered an `Issues' or bug tracker board that became very useful towards the end of our project, a mailing list service that we used to share ideas and problems that we had and a download section so we could share any papers we thought might have been useful.

The integrated development environment (IDE) Eclipse was chosen to develop the program with for several reasons. The IDE helps with code completion, debugging code and many other routine task such as creating initial class files. It basically provides a graphically environment for which one can develop in. It also integrates well with SVN through the use of \textit{Subclipse}, an eclipse SVN plug-in, providing a graphical interface to check in and check out versions from the repository. As the majority of the team had never used SVN before, having a GUI front-end to SVN meant less time learning tools and hence shifted the attention to the project at hand. Eclipse also has Javadoc integration, meaning that the information written in Javadoc by team members about our code was available on the fly. This made coding much easier, as we did not have to search through the documentation files to find information about code written by other team members. Although it was not crucial that all the team members used Eclipse we felt that it was wise to have everybody developing in the same environment.

\newpage 
\section{Conclusion}
%Summaraise, extent of success and what we have learnt group skills wise and quantum wise.
%our first group project, developed skills that would be invaluable should another group project be attempted.
In this project we have succeeded in all of our initial aims. We now have a working understanding of the current state of the field of quantum computing, and can discuss qubits, registers, gates and algorithms with some level of knowledge. We have successfully written a simulation of a quantum computer in Java, simulating a large number of different quantum gates in different ways, and have then implemented Grover's algorithm as an example of using this simulator. This was all achieved through working together closely as a team, using a variety of techniques and tools to ensure that all team members' work was coordinated and working towards the overall goals of the project. 

Our simulator has been designed in such a way that the underlying code could be reused to implement any quantum algorithm. We have simulated a Turing-complete set of basic quantum gates, complete with full documentation detailing their fields and methods, meaning that anyone who had access to our code would be able to use them to create their own quantum computer simulation. We have also learnt how to use Subversion, Eclipse and Javadoc as part of a group project, as well as having the significance of a well planned and structured program reinforced, which will put us in good stead for any future group projects.



\newpage
\section{References}
\vspace{-22pt}
\renewcommand*{\refname}{}


\bibliography{ref}
\bibliographystyle{ieeetr}





\newpage
\section{Appendices}
\subsection{UML}\label{uml}
\begin{center}
    \includegraphics[scale=0.8 , trim=0 400 0 0]{UML}
    \captionof{figure}{UML diagram of code structure.}
\end{center}

\subsection{GUI}
The user interface of the project was fully graphical and consisted of two different frames. The first was an initial interface asking for certain values in order to begin the simulation, seen in Figure \ref{intropanel}.

\begin{center}
	\includegraphics[scale=0.5]{Intro-QuantumComputer.png}
	\captionof{figure}{Intro panel shown when the program is initially run.}
	\label{intropanel}
\end{center}

The second interface is that of the simulation itself. From figure \ref{mainui}, the larger text-box at the top of the display provides all information needed as the simulation is running. To the right of this, the user can select the configuration of gates to be run in the system. The large plot on the left-hand side of the display shows the probabilities of the states throughout the simulation. The plot to the right of this is the rotation of states representation described in Figure \ref{rotfig}. The bottom most panel provides the buttons the user needs to click to perform the simulation.

\begin{center}
	\includegraphics[scale=0.4]{Screenshot-QuantumComputer.png}
	\captionof{figure}{The main user interface showing the simulation.}
	\label{mainui}
\end{center}

\subsection{Factory Constructor}\label{factory}
Factory methods were utilised extensively within the \texttt{gates} package in our code. The provide a very simple solution to the problem of deciding which object needs initialising. Factory methods can easily be explained in the context of our report.

Given the Hadamard gate, in our simulation this gate can either be represented as a matrix or a function, with each representation taking a different class, \texttt{HamadardMatrix} and \texttt{HadamardFunction} respectively. If one wants to construct a Hadamard gate, they must choose the appropriate constructor to either create a matrix or functional representation. They can do this explicitly by calling the constructor directly, but their choice of representation is hard-coded and can only be changed by modifying all the calls to that constructor. There is no way to chose the representation automatically without the person creating the Hadamard object having to choose the representation.

Factory methods solve this problem by creating static methods that return a Hadamard gate, choosing the representation. Factory methods are usually in a static, non-instantiateable class, in our case called \texttt{Factory}. The static method is called and, depending on static variable in this methods, a representation of the Hadamard matrix is created, cast as a \texttt{Gate} object and returned to the user. The user may not even be aware that such a decision has been made for them as it bares no relevance to them, they are only interested in obtaining a Hadamard gate regardless on representation. In our program, all the constructors have also been set to \texttt{protected}, and hence only accessible to the \texttt{Factory} class, to insist on the use of factor methods.
\lstset{language=java,basicstyle=\footnotesize,frame=single}
\begin{figure}[h]
\begin{lstlisting}
/**
* Static boolean that determines if a functional representation is returned or not.
* By default, this is set to true as there are performance benefits.
*/
public static boolean functional = true;

/**
* Create a hadamard <code>Gate</code> object and return to the user.
* @param target Target bits
*/
public static Gate createHadamard(int target){
	if(functional){
		return (Gate)new HadamardFunction(target);
	}
	else {
		return (Gate)new HadamardMatrix(target);
	}
}
\end{lstlisting}
\captionof{figure}{The static factory method in the \texttt{Factory} class called to construct a Hadamard gate. The method will create a Hadamard gate represented by either a matrix or function depending on whether the static boolean \texttt{functional} is set to true or false. Note, the user creating the Hadamard never needs to be aware of this decision.}
	\label{code}
\end{figure}
\\
\\
\\


\end{document}

